package _06_动态规划;

import java.util.Arrays;

public class _322_零钱兑换 {

    // dp＋排序（效率也没有那么明显的提升）
    public int coinChange2(int[] coins, int amount) {
        Arrays.sort(coins);
        // 表示凑i枚硬币，需要的最小硬币个数
        int[] dp = new int[amount + 1];
        // 设置兑换硬币的最大值
        Arrays.fill(dp, amount + 1);
        // 初始化硬币数量
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin > i) break;
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    // 相对于最优解
    public int coinChange(int[] coins, int amount) {
        // 表示凑i枚硬币，需要的最小硬币个数
        int[] dp = new int[amount + 1];
        // 设置兑换硬币的最大值
        Arrays.fill(dp, amount + 1);
        // 初始化硬币数量
        dp[0] = 0;
        // i = coin是比较重要的步骤
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    // dp, 需要明白，如果硬币数量的最小面值都是10，那么1-9的硬币兑换显然没那么必要了
    public int coinChange1(int[] coins, int amount) {
        // 表示凑i枚硬币，需要的最小硬币个数
        int[] dp = new int[amount + 1];
        // 设置兑换硬币的最大值
        Arrays.fill(dp, amount + 1);
        // 初始化硬币数量
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

}
